<?

  require_once 'Tree.class.php';

  class HOGTree extends Tree
  {
    public $id  = null; // node ID
    public $spc = null; // species name (if the node is a leaf)
    public $len = null; // upgoing branch length (distance to parrent)
    public $bs  = null; // bootstrap value (if the node is not a leaf)
    public $alc = null; // non-bacterial leaves count
    public $blc = null; // bacterial leaves count
    public $d   = null; // measure of antiquity ('d' defined in req.spec.)

    public static $bacIDs;
    public static $maxID=0;

    public function __construct( Tree $source, HOGTree $parent=null )
    {
      parent::__construct( $source->label, $parent );
      $this->id   = ++HOGTree::$maxID;
      $this->info = $source->info;
      foreach ( $source->children as $child )
        new HOGTree( $child, $this );
      $this->parseLabel();
      $this->defineStats();
    }

    private function parseLabel()
    {
      $label = $this->label;

      // branch length
      if ( preg_match( "~:(\d+(\.\d+)?(e-\d+)?)$~", $label, $parts ) )
      {
        $this->len = floatval( $parts[1] );
        $label = preg_replace( "~:$parts[1]$~", "", $label );
      }

      if ( $this->isLeaf() )
        if ( empty($label) )
          $this->spc = $label;
        elseif ( preg_match( "~^([a-z]+)[0-9]*(_|$)~i", $label, $parts ) )
          $this->spc = $parts[1];
        else
          echo "Strange leaf label: '$label',\n";
      else
        if ( empty($label) )
          $this->bs = -1;
        elseif ( preg_match( "~^[0-9]+$~", $label ) )
          $this->bs = intval($label);
        else
          echo "Strange non-leaf label: '$label'.\n";

      $this->label = $label;
    }

    private function defineStats( $noCache = false )
    {
      $this->alc = $this->numberOfLeaves( $noCache );
      $this->blc = $this->numberOfBacLeaves( $noCache );
    }

    private function refreshStats()
    {
      $this->defineStats( /* $noCache = */ true );
    }

    public function root()
    {
      if ( $this->isRoot() )
        return $this;
      else
        return $this->parent->root();
    }

/*
    public function getSpeciesList()
    {
      if ( $this->isLeaf() )
        return array( $this->spc );

      $spList = array();
      foreach ( $this->children as $child )
        $spList = array_merge( $spList, $child->getSpeciesList() );
      return $spList;
    }
*/

    public function numberOfLeaves( $noCache = false )
    {
      if ( !$noCache and $this->alc !== null )
        return $this->alc;
      $nb = 0;
      if ( $this->isLeaf() )
        return 1;
      else
        foreach ( $this->children as $child )
          $nb += $child->numberOfLeaves( $noCache );
      return $nb;
    }

    public function numberOfBacLeaves( $noCache = false )
    {
      if ( !$noCache and $this->blc !== null )
        return $this->blc;
      $nb = 0;
      if ( $this->isLeaf() )
        return ( $this->isBacterium() ? 1 : 0 );
      else
        foreach ( $this->children as $child )
          $nb += $child->numberOfBacLeaves( $noCache );
      return $nb;
    }

    public function isBacterium()
    {
      if ( !$this->isLeaf() )
        return false;
      else
        return in_array( $this->spc, self::$bacIDs );
    }

    public function hasNonBacLeaf()
    {
      return $this->alc - $this->blc > 0;
    }

    public function calcD_rec()
    {
      $this->calcD();
      if ( !$this->isLeaf() )
        foreach ( $this->children as &$child )
          $child->calcD_rec();
    }

    public function calcD()
    {
      if ( $this->isRoot() )
        return;
      $l1 = $this->alc;
      $l0 = $this->root()->alc - $l1;
      $b1 = $this->blc;
      $b0 = $this->root()->blc - $b1;
      $d1 = $b1/$l1;
      $d0 = $b0/$l0;
      $d = pow( sqrt($d1) - sqrt($d0), 2 );
      $this->d = $d;
    }

    public function getDList()
    {
      $dList = array();

      if ( !$this->isRoot() )
        $dList[] = array( $this->d, $this );

      foreach ( $this->children as $child )
        $dList = array_merge( $dList, $child->getDList() );

      return $dList;
    }

/*
    public function getNodeByID( $nid )
    {
      if ( $this->id === $nid )
        return $this;
      else
        if ( !$this->isLeaf() )
          foreach ( $this->children as &$child )
            if ( $node = $child->getNodeByID( $nid ) )
              return $node;
      return false;
    }
*/

    public function & getParent()
    {
      return $this->parent;
    }

/*
    public function unlinkChildByID( $id )
    {
      if ( !$this->isLeaf() )
        foreach ( $this->children as $cn => &$child )
          if ( $child->id === $id )
          {
            $child->forgetParent(); // making the child to forget it's parent
            unset( $this->children[$cn] ); // removing child from children array
            $this->children = array_merge( $this->children ); // re-indexing the array
            break;
          }
    }
*/

    public function removeChild( $theChild )
    {
      if ( !$this->isLeaf() )
        foreach ( $this->children as $cn => &$child )
          if ( $child === $theChild )
          {
            $child->destroy(); // destroying the child to free memory
            unset( $this->children[$cn] ); // removing child from children array
            $this->children = array_merge( $this->children ); // re-indexing the array
            break;
          }
    }

    public function unlinkChild( $theChild )
    {
      if ( !$this->isLeaf() )
        foreach ( $this->children as $cn => &$child )
          if ( $child === $theChild )
          {
            $child->forgetParent(); // making the child to forget it's parent
            unset( $this->children[$cn] ); // removing child from children array
            $this->children = array_merge( $this->children ); // re-indexing the array
            break;
          }
    }

    public function forgetParent()
    {
      $this->parent = null;
    }

    public function becomeRoot()
    {
      if ( $this->isRoot() )
        return;
      $parent = $this->parent;
      $parent->unlinkChild( $this );
      $parent->becomeRoot();
      $this->addChild( $parent );
    }

    public function removeNonBacLeaves( $recursiveCall = false )
    {
      if ( !$this->isLeaf() )
        foreach ( $this->children as &$child )
          if ( $child->blc < 1 )
            $this->removeChild( $child );
          else
            $child->removeNonBacLeaves( /* $recursiveCall = */ true );
      if ( !$recursiveCall )
        $this->root()->defineStats();
      // ?? discuss removing "transit nodes" ??
    }

    public function toNewickCompact( $root=true )
    {
      $label = $this->label;
      $this->label = $this->isLeaf() ?
                     ( $this->isBacterium() ? "[B]" : "[N]" ) . $this->spc :
                     ( $this->bs >= 0 ? $this->bs : "" );
      $result = parent::toNewickCompact( false );
      $this->label = $label;

      if ( $root )
        $result .= ';';

      return $result;
    }

  }

  HOGTree::$bacIDs = null;

?>
